The present invention relates to computer architecture. More particularly, the invention relates to branch prediction.
Computer processors often employ pipelining to increase performance. “Pipelining” refers to a processing technique in which multiple sequential instructions are executed in an overlapping manner. Thus, when program flow is substantially sequential, a pipelined architecture may achieve significant performance advantages over non-pipelined architecture. In actual programs, however, a significant percentage of program instructions are branches. Branch instructions cause a program to deviate from a sequential flow. Therefore, the instruction to be executed (i.e. the target of the branch) may not be the next instruction in the fetch sequence.
One approach to solving this problem, called branch prediction, involves making accurate, educated determinations about whether an instruction will result in a branch to another location. Branch prediction is premised on the assumption that, under similar circumstances, the outcome of a conditional branch will likely be the same as prior outcomes. However, all speculative tasks beyond a branch must be thrown away if that branch is mispredicted. Therefore an accurate branch prediction technique is important to deeply pipelined processors.
Hybrid branch predictors have been introduced as a way to achieve higher prediction accuracies. The hybrid branch predictor combines multiple prediction schemes into a single predictor. A selection mechanism is used to decide for each branch, which single-scheme predictor to use. An effective hybrid branch predictor may exploit the different strengths of its single-scheme predictor components, enabling it to achieve a prediction accuracy greater than that which could be achieved by any of its components alone. Since the selection mechanism of the hybrid branch predictor selects prediction of only one predictor at a particular branch, information generated by other predictors at the same branch may be redundant. Accordingly, the existing hybrid branch prediction scheme may promote inefficient utilization of memory space in the storage arrays of the branch prediction.